package 贪心;

import java.util.Arrays;

/**
 * 该题有点类似于
 * 最优子装载的问题，
 * 好像也可以使用动态规划来写
 * 能用 dp 的话 大概率是 能 写出来  
 * 暴力递归的！
 * 除了   leetcode **子数组的最大和**    那个问题没有写出来，暴力递归之外，
 *  从当前这个题的 写题的过程中 ，可以发散的去理解一下其他的东西！
 */
public class leetcode11月15日每日一题 {
	/**
	 * 	最优子装载问题的 一个变种问题!
	 * 	从这题 当中能看到 很多题的影子
	 */
	
	public static void main(String []args) {
		int choice[][] = {{3,2},{2,3},{5,2}};
		int counts = 6;
		int len = choice.length;
		System.out.println(solution(choice,counts));
		System.out.println(recursion(0,counts,len,choice));
		System.out.println(dp(choice,counts));
		System.out.println(dpFinal(choice,counts));
	}
	
	// 贪心
	public static int solution(int choice[][],int count) {
		
		// 先对 二维数组 针对  choice[][1] 进行排序
		Arrays.sort(choice,(a,b) -> b[1] - a[1] );
		for(int num[] : choice)
			System.out.println(Arrays.toString(num));
		int sum = 0;
		for(int i = 0;i < choice.length;i++) {
			if(count - choice[i][0] > 0) {
				count -= choice[i][0];
				sum += choice[i][0] * choice[i][1];
			}
			else {
				sum += choice[i][1] * count;
				break;
			}
				
		}
		return sum;
	}
		
	// 暴力递归
	/**
	 * 通过这个暴力递归的编写 还是想明白很多东西!
	 * 首先对 这个 递归函数 , 做一个简单的说明
	 * f(index,counts)( return int (当前层的递归返回的 值,就是 index ,counts 时表示的最优解) ) 
	 * 表示的意义是: 在 index ,counts 时一个 最优解的值 
	 */
	public static int recursion(int index,int counts,int len,int choice[][]) {
		if(index == len)
			return 0;
		int ans = 0;
		for(int count = 0;count <= choice[index][0] && counts - count >= 0; count++) {
			int tempAns = recursion(index + 1,counts - count,len,choice) + count * choice[index][1];
			ans = Math.max(ans, tempAns);
		}
		return ans;
	}
	
	/**
	 * 改写 成dp
	 * 
	 * 这个 有点类似 于多重 背包的 问题 ,并不是 只能选择一次, 也并不能选 无数次,
	 * 多重背包
	 */
	public static int dp(int choice[][],int counts) {
		int len = choice.length;
		int dp[][] = new int [len + 1][counts + 1];
		
		// 没什么要初始化的basecase 
		// 开始填表
		for(int index = len - 1;index >= 0;index --) {
			
			for(int cnt = 0;cnt <= counts;cnt++) {
				
				int ans = 0;
				for(int count = 0; count <= choice[index][0] && cnt - count >= 0; count++) {
					ans = Math.max(ans, dp[index + 1][cnt - count] + count * choice[index][1]);
				}
				dp[index][cnt] = ans;
			}
			
		}
		for(int arr[] : dp)
			System.out.println(Arrays.toString(arr));
		return  dp[0][counts];
	}
	/**
	 * 把内部的 这个 枚举行为 也给它省掉 ( 斜率 优化 )
	 * 这个题根本就斜率优化不了吧
	 * 优化不出来 ！
	 * 下面这是错误的 写法， 这种斜率优化 还是 去 看一个  ** 货币面值 ** 这个题最好！ 
	 */
	public static int dpFinal(int choice[][],int counts) {
		int len = choice.length;
		int dp [][] = new int [len + 1][counts + 1];
		for(int index = len - 1;index >= 0 ;index --) {
			for(int cnt = 0;cnt <= counts ;cnt++) {
				dp[index][cnt] = dp[index + 1][cnt] ;//+ cnt * choice[index][1];
				if(cnt - 1 >= 0)
					dp[index][cnt] = Math.max(dp[index][cnt], cnt - choice[index][0] <= 0 ? 
							dp[index][cnt - 1] + choice[index][1] : dp[index][cnt - 1]);
//					dp[index][cnt] = Math.max(dp[index][cnt], dp[index][cnt - 1] + choice[index][1]);
			}
		}
		for(int arr[] : dp)
			System.out.println(Arrays.toString(arr));
		return dp[0][counts];
	}
	
	
}
